package DataStructure.LinkedLearning.SingleLinkedList.LinearList;

/**
 *  使用内部类封装链表
 */
public class MySingleLinked {
    // 定义头节点和长度
    private Node head;
    private int size;

    /**
     *  添加功能，将新节点添加到链表末尾
     * @param str 新节点内容
     * @return  返回成功与否
     */
    public boolean add(String str) {
        // 判断新节点内容是否为空，空则报错
        if(str == null) {
            throw new IllegalArgumentException("The parame is null");
        }
        Node node = new Node(str, null);
        if(size == 0) {
            head = node;
            size++;
            return true;
        }
        // 创建标记节点 用于后移查找
        Node mid = head;
        while(mid.next != null) {
            mid = mid.next;
        }
        mid.next = node;
        size++;
        return true;
    }

    /**
     *  根据下标添加新节点至下标位置（下标从0开始）
     * @param index 下标
     * @param str   新节点内容
     * @return  返回成功与否
     */
    public boolean add(int index, String str) {
        // 验证参数是否合法
        if (index < 0 || index > size) {
            throw  new IllegalArgumentException("index is Illegal");
        }
        Node node = new Node(str, null);
        // 添加头结点
        if (index == 0){
            node.next = head;
            head = node;
            size++;
            return true;
        }
        // 添加的不是头结点
        int tag = 1;
        Node mid = head;
        while (tag < index){
            mid = mid.next;
            tag++;
        }
        // 要添加的元素, 是添加到mid之后
        mid.next = new Node(str, mid.next);
        size++;
        return true;
    }

    /**
     *  删除功能 根据指定的内容删除第一个匹配的节点
     * @param str   指定的内容
     * @return  返回删除的内容
     */
    public String delete(String str) {
        // 判断链表是不空
        if (size == 0){
            throw new RuntimeException("The linked is null");
        }
        // 判断删除的是否是头结点
        if (head.value.equals(str)){
            String oldValue = head.value;
            head = head.next;
            size--;
            return oldValue;
        }
        // 删除不是头结点
        Node mid = head;
        // 向后移动查找位置:
        // 直到找到 mid的下一个元素是null
        // 或者mid的下一个元素的value就是和str的参数equals
        while (mid.next != null && !mid.next.value.equals(str)){
            mid = mid.next;
        }
        // 如果跳出循环是因为mid到达末尾
        if (mid.next == null){
            return null;
        }
        // 否则跳出循环是因为找到了匹配的内容
        // 删除mid.next
        String oldValue = mid.next.value;
        mid.next = mid.next.next;
        size--;
        return oldValue;
    }

    /**
     *  删除功能 根据下标删除节点
     * @param index 下标
     * @return  返回删除的内容
     */
    public String delete(int index) {
        // 判断传入的参数
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("The parame is Illegal");
        }
        // 如果删除的是头节点
        if(index == 0) {
            String oldValue = head.value;
            head = head.next;
            size--;
            return oldValue;
        }
        // 删除的不是头节点
        int tag = 1;
        Node mid = head;
        while (tag < index){
            mid = mid.next;
            tag++;
        }
        // 删除的是mid.next;
        String oldValue = mid.next.value;
        mid.next = mid.next.next;
        size--;
        return oldValue;
    }

    /**
     *  替换功能 根据指定内容替换第一个匹配的节点内容
     * @param oldValue  指定内容
     * @param newValue  新内容
     * @return  返回成功与否
     */
    public boolean set(String oldValue, String newValue) {
        // 判空
        if (size == 0){
            throw new RuntimeException("The linked is null");
        }
        // 要替换, 先找到对应结点
        Node mid = head;
        // 遍历的元素不是null(后面还有元素可以遍历),  并且遍历的元素和查找的值不相等
        while (mid != null && ! oldValue.equals(mid.value)){
            mid = mid.next;
        }
        // 如果跳出循环是因为mid移至末尾
        if (mid == null){
            return false;
        }
        // 否则跳出循环是因为mid匹配到指定内容
        // mid就是要替换的元素
        mid.value = newValue;
        return true;
    }

    /**
     * 根据下标替换一个元素
     * @param index : 要替换的下标位置
     * @param newValue:  替换的新值
     * @return : 被替换的旧值
     */
    public String set(int index, String newValue){
        // 判空
        if(size == 0) {
            throw new RuntimeException("The linked is null");
        }
        // 判断传入的参数
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("The parame is Illegal");
        }
        // 要替换, 先找到对应结点
        int tag = 0;
        Node mid = head;
        // 遍历的元素不是null(后面还有元素可以遍历),  并且遍历的元素和查找的值不相等
        while (mid != null && tag != index ){
            mid = mid.next;
            tag++;
        }
        // 如果跳出循环是因为mid移至末尾
        if (mid == null){
            return null;
        }
        // 否则跳出循环是因为mid匹配到指定内容
        // mid就是要替换的元素
        String oldValue = mid.value;
        mid.value = newValue;
        return oldValue;
    }

    /**
     * 判断一个元素在链表中是否存在
     * @param str:  要判断的元素
     * @return : Exist or not
     */
    public boolean contains(String str){
        // 判空
        if (size == 0) {
            throw new RuntimeException("linked is  null");
        }
        Node mid = head;
        // 遍历的元素不是null(后面还有元素可以遍历),  并且遍历的元素和查找的值不相等
        while (mid != null && ! str.equals(mid.value)){
            mid = mid.next;
        }
        // 1, mid = null
        if (mid == null){
            return false;
        }
        return true;
    }

    /**
     * 根据下标查找一个值
     * @param index : 要查找的下标
     * @return: 这个下标对应的值
     */
    public String get(int index) {
        // 判空
        if (size == 0) {
            throw new RuntimeException("linked is null");
        }
        // 判断参数
        if(index <0 || index >= size) {
            throw  new IllegalArgumentException("The index is Illegal");
        }
        int tag = 0;
        Node mid = head;
        // 遍历的元素不是null(后面还有元素可以遍历),  并且遍历的元素和查找的值不相等
        while (mid != null && tag != index){
            mid = mid.next;
            tag++;
        }
        if (mid == null){
            return null;
        }
        return mid.value;
    }

    @Override
    public String toString() {
        return "{" +
                "head=" + head +
                ", size=" + size +
                '}';
    }

    // 内部类封装链表
    class Node {
        String value;
        Node next;

        public Node(String value, Node next) {
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            return "{" +
                    "v='" + value + '\'' +
                    ", n=" + next +
                    '}';
        }
    }
}
